package org.example;

public class Test2 {
    //leetcode 115 不同的子序列 https://leetcode.cn/problems/distinct-subsequences/description/
    public int numDistinct(String s, String t) {
        int MOD = (int) 1e9 + 7;
        //题目解析，因为题目要求在s的子序列中找到t字符串出现的次数，s是子序列，而t是字符串，所以s字符串的遍历就作为内部遍历
        char[] arr1 = s.toCharArray(), arr2 = t.toCharArray();
        int n1 = arr1.length, n2 = arr2.length;
        //dp数组的含义就是t[0,i]的字符串在s[0,j]之间的子序列出现的次数
        int[][] dp = new int[n2+1][n1+1];
        for (int i = 0; i <= n1; i++) dp[0][i] = 1;
        for (int i = 1; i <= n2; i++) {
            for (int j = 1; j <= n1; j++) {
                //不考虑arr1[j-1]，看arr[0,j-2]之家的子序列t[0,i]出现了几次
                dp[i][j] = dp[i][j-1];
                //考虑arr1[j-1],那么就需要arr1[j-1]==arr2[i-1]
                if (arr1[j-1] == arr2[i-1]) {
                    dp[i][j] += dp[i-1][j-1] % MOD;
                }
            }
        }
        return dp[n2][n1];
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        String s1 = "rabbbit";
        String s2 = "rabbit";
        test2.numDistinct(s1,s2);
        System.out.println(666);
    }
}
